/**
 * 
 */
package edu.umd.clip.lm.model;

import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.Map;
import java.util.regex.Pattern;

import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import javax.xml.parsers.ParserConfigurationException;

import org.w3c.dom.Document;
import org.w3c.dom.Element;
import org.w3c.dom.NodeList;
import org.w3c.dom.bootstrap.DOMImplementationRegistry;
import org.w3c.dom.ls.DOMImplementationLS;
import org.w3c.dom.ls.LSOutput;
import org.w3c.dom.ls.LSSerializer;
import org.xml.sax.SAXException;

import edu.umd.clip.lm.factors.*;
import edu.umd.clip.lm.model.training.*;
import edu.umd.clip.lm.util.BinaryPrefix;
import edu.umd.clip.lm.util.IO;
import edu.umd.clip.lm.util.XMLUtils;
import edu.umd.clip.lm.util.tree.*;

/**
 * @author Denis Filimonov <den@cs.umd.edu>
 *
 */
public class Experiment {
	public static final String XML_ROOT_ELEMENT_NAME = "experiment";
	public static final String XML_CONFIG_ELEMENT_NAME = "configuration";
	public static final String XML_CONFIG_TRAINING_ELEMENT_NAME = "training";
	public static final String XML_CONFIG_CLASSES_ELEMENT_NAME = "classes";
	public static final String XML_CONFIG_FILES_ELEMENT_NAME = "files";
	
	public static final String XML_CONFIG_TRAINER_CLASS_ELEMENT_NAME = "trainer";
	public static final String XML_CONFIG_PARSER_CLASS_ELEMENT_NAME = "tuple-parser";
	public static final String XML_CONFIG_LM_CLASS_ELEMENT_NAME = "lm";

	private static Experiment instance = null;
	private Document doc = null;
	private HashMap<String,LanguageModel> LMs = new HashMap<String,LanguageModel>();
	private HashMap<String,ForestModel> forests = new HashMap<String,ForestModel>();
	
	private LanguageModel LMsById[];
	//private int lmIdSequence[];
	
	private InputParser tupleParser = null;
	private FactorTupleDescription tupleDescription = null;
	
	private HFT<HFTPayload> hft;
	private HashMap<FactorTuple, BinaryPrefix> hiddenPrefixes;
	private WordTree<WordTreePayload> wordTree;
	private BinaryPrefix[] wordPrefixes;

	private BinaryPrefix[] compactHiddenPrefixes;
	private HashMap<BinaryPrefix, byte[]> prefix2CompactHiddenFactors;
	
	private HashMap<BinaryPrefix, BinaryPrefix> prefixCache = new HashMap<BinaryPrefix, BinaryPrefix>(10000);
	private int debugDecoder = 0;
	private Files files;
	
	private Experiment() {
		DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance();
		DocumentBuilder db = null;
		try {
			db = dbf.newDocumentBuilder();
		} catch (ParserConfigurationException e) {
			e.printStackTrace();
			return;
		}
		doc = db.newDocument();
	}

	private Experiment(String configfile) throws IOException {
			this(IO.getInputStream(configfile));
	}
	
	private Experiment(InputStream configfile) {
		DocumentBuilderFactory dbf = DocumentBuilderFactory.newInstance();
		DocumentBuilder db = null;
		try {
			db = dbf.newDocumentBuilder();
		}catch(ParserConfigurationException pce) {
			pce.printStackTrace();
			return;
		}
		try {
			doc = db.parse(configfile);
			parseXML();
		} catch (SAXException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (doc == null) {
			doc = db.newDocument();
		}
	}
	
	public void closeXML() {
		doc = null;
	}
	
	private void parseXML() {
		Element configElement = getConfigElement();
		Element section;
		
		section = XMLUtils.getFirstElementByTagName(configElement, Files.FILES_SECTION);
		if (section != null) {
			files = new Files(section);
		}
	}
	
	public Files getFiles() {
		if (files == null) {
			files = new Files();
		}
		return files;
	}
	
	public static class Files {
		private ArrayList<String> dataFiles;
		private ArrayList<int[]> trainData;
		private ArrayList<int[]> smoothData;
		private ArrayList<int[]> interpolateData;
		
		private String db;
		
		private static final String FILES_SECTION = "files";
		private static final String DATA_FILE = "data-file";
		private static final String TRAIN = "train";
		private static final String INTERPOLATE = "interpolate";
		private static final String SMOOTH = "smooth";
		private static final String DB = "db";
		private static final Pattern split_re = Pattern.compile(",");
		
		private Files() {}
		
		private Files(Element xmlnode) {
			assert(xmlnode.getNodeName().equals(FILES_SECTION));
			Element file;
			NodeList list;
			
			file = XMLUtils.getFirstElementByTagName(xmlnode, DB);
			if (file != null) {
				db = file.getTextContent();
			}
			
			list = XMLUtils.getChildrenElementsByTagName(xmlnode, DATA_FILE);
			if (list != null && list.getLength() > 0) {
				dataFiles = new ArrayList<String>(list.getLength());
				for(int i=0; i<list.getLength(); ++i) {
					file = (Element) list.item(i);
					dataFiles.add(file.getTextContent());
				}
			}
			
			list = XMLUtils.getChildrenElementsByTagName(xmlnode, TRAIN);
			if (list != null && list.getLength() > 0) {
				trainData = new ArrayList<int[]>(list.getLength());
				for(int i=0; i<list.getLength(); ++i) {
					file = (Element) list.item(i);
					String fileNums[] = split_re.split(file.getTextContent());
					int[] nums = new int[fileNums.length];
					for(int n=0; n<nums.length; ++n) {
						nums[n] = Integer.parseInt(fileNums[n]);
					}
					trainData.add(nums);
				}				
			}
			
			list = XMLUtils.getChildrenElementsByTagName(xmlnode, SMOOTH);
			if (list != null && list.getLength() > 0) {
				smoothData = new ArrayList<int[]>(list.getLength());
				for(int i=0; i<list.getLength(); ++i) {
					file = (Element) list.item(i);
					String fileNums[] = split_re.split(file.getTextContent());
					int[] nums = new int[fileNums.length];
					for(int n=0; n<nums.length; ++n) {
						nums[n] = Integer.parseInt(fileNums[n]);
					}
					smoothData.add(nums);
				}				
			}
			
			list = XMLUtils.getChildrenElementsByTagName(xmlnode, INTERPOLATE);
			if (list != null && list.getLength() > 0) {
				interpolateData = new ArrayList<int[]>(list.getLength());
				for(int i=0; i<list.getLength(); ++i) {
					file = (Element) list.item(i);
					String fileNums[] = split_re.split(file.getTextContent());
					int[] nums = new int[fileNums.length];
					for(int n=0; n<nums.length; ++n) {
						nums[n] = Integer.parseInt(fileNums[n]);
					}
					interpolateData.add(nums);
				}				
			}
			
		}
		
		private Element toXML(Document doc) {
			Element files = doc.createElement(FILES_SECTION);
			Element elem;
			
			if (db != null) {
				elem = doc.createElement(DB);
				elem.setTextContent(db);
				files.appendChild(elem);
			}

			if (dataFiles != null) {
				for(String file : dataFiles) {
					elem = doc.createElement(DATA_FILE);
					elem.setTextContent(file);
					files.appendChild(elem);
				}
			}
			
			if (trainData != null) {
				for(int [] data : trainData) {
					assert(data.length > 0);
					StringBuilder sb = new StringBuilder();
					sb.append(data[0]);
					for(int i=1; i<data.length; ++i) {
						sb.append(',');
						sb.append(data[i]);
					}
					elem = doc.createElement(TRAIN);
					elem.setTextContent(sb.toString());
					files.appendChild(elem);
				}
			}
			
			if (smoothData != null) {
				for(int [] data : smoothData) {
					assert(data.length > 0);
					StringBuilder sb = new StringBuilder();
					sb.append(data[0]);
					for(int i=1; i<data.length; ++i) {
						sb.append(',');
						sb.append(data[i]);
					}
					elem = doc.createElement(SMOOTH);
					elem.setTextContent(sb.toString());
					files.appendChild(elem);
				}
			}
			
			if (interpolateData != null) {
				for(int [] data : interpolateData) {
					assert(data.length > 0);
					StringBuilder sb = new StringBuilder();
					sb.append(data[0]);
					for(int i=1; i<data.length; ++i) {
						sb.append(',');
						sb.append(data[i]);
					}
					elem = doc.createElement(INTERPOLATE);
					elem.setTextContent(sb.toString());
					files.appendChild(elem);
				}
			}

			return files;
		}

		public String getDb() {
			return db == null ? "data" : db;
		}

		public void setDb(String db) {
			this.db = db;
		}

		public ArrayList<String> getDataFiles() {
			return dataFiles;
		}

		public void setDataFiles(ArrayList<String> dataFiles) {
			this.dataFiles = dataFiles;
		}

		public ArrayList<int[]> getTrainData() {
			return trainData;
		}

		public void setTrainData(ArrayList<int[]> trainData) {
			this.trainData = trainData;
		}

		public String[] getTrainDataFiles(int split) {
			int[] fileNums = trainData.get(split);
			String[] files = new String[fileNums.length];
			for(int i=0; i<fileNums.length; ++i) {
				files[i] = dataFiles.get(fileNums[i]);
			}
			return files;
		}
		
		public ArrayList<int[]> getSmoothData() {
			return smoothData;
		}

		public void setSmoothData(ArrayList<int[]> smoothData) {
			this.smoothData = smoothData;
		}

		public String[] getSmoothDataFiles(int split) {
			int[] fileNums = smoothData.get(split);
			String[] files = new String[fileNums.length];
			for(int i=0; i<fileNums.length; ++i) {
				files[i] = dataFiles.get(fileNums[i]);
			}
			return files;
		}
		
		public ArrayList<int[]> getInterpolateData() {
			return interpolateData;
		}

		public void setInterpolateData(ArrayList<int[]> interpolateData) {
			this.interpolateData = interpolateData;
		}

		public String[] getInterpolateDataFiles(int split) {
			int[] fileNums = interpolateData.get(split);
			String[] files = new String[fileNums.length];
			for(int i=0; i<fileNums.length; ++i) {
				files[i] = dataFiles.get(fileNums[i]);
			}
			return files;
		}
		
	}
	
	public void saveConfig(String configfile) throws IOException {
		try {
			Element rootElement = doc.getDocumentElement();
			if (rootElement == null) {
				rootElement = doc.createElement(XML_ROOT_ELEMENT_NAME);
				doc.appendChild(rootElement);
			}
			Element configElement = getConfigElement();

			if (files != null) {
				configElement.appendChild(files.toXML(doc));
			}
			
			if (LMs.size() > 0) {
				NodeList nodes = XMLUtils.getChildrenElementsByTagName(configElement, LanguageModel.XML_ELEMENT_NAME);
				for(int i=0; i<nodes.getLength(); ++i) {
					configElement.removeChild(nodes.item(i));
				}
				for(LanguageModel lm : LMs.values()) {
					configElement.appendChild(lm.createXML(doc));
				}
			}
			
			if (forests.size() > 0) {
				NodeList nodes = XMLUtils.getChildrenElementsByTagName(configElement, ForestModel.XML_ELEMENT_NAME);
				for(int i=0; i<nodes.getLength(); ++i) {
					configElement.removeChild(nodes.item(i));
				}
				for(ForestModel forest : forests.values()) {
					configElement.appendChild(forest.createXML(doc));
				}				
			}
			
			if (tupleDescription != null) {
				configElement.replaceChild(tupleDescription.createXML(doc), getTupleDescriptionConfig());
			}
			
			Element classElement = getClassesConfig();
			
			{
				Element old = XMLUtils.getFirstElementByTagName(classElement, XML_CONFIG_LM_CLASS_ELEMENT_NAME);
				Element n = doc.createElement(XML_CONFIG_LM_CLASS_ELEMENT_NAME);
				n.setTextContent(LanguageModel.class.getCanonicalName());
	
				if (old == null) {
					classElement.appendChild(n);
				} else {
					classElement.replaceChild(n, old);
				}
			}
			
			if (tupleParser != null) {
				NodeList nl = classElement.getElementsByTagName(XML_CONFIG_PARSER_CLASS_ELEMENT_NAME);
				Element e = doc.createElement(XML_CONFIG_PARSER_CLASS_ELEMENT_NAME);
				e.setTextContent(tupleParser.getClass().getCanonicalName());
				if (nl == null || nl.getLength() == 0) {
					classElement.appendChild(e);
				} else {
					classElement.replaceChild(e, nl.item(0));
				}
			}
			if (hft != null) {
				Element e = XMLUtils.getFirstElementByTagName(configElement, HFT.XML_ELEMENT_NAME);
				if (e != null) {
					configElement.replaceChild(hft.createXML(doc), e);
				} else {
					configElement.appendChild(hft.createXML(doc));
				}
			}
			if (wordTree != null) {
				Element e = XMLUtils.getFirstElementByTagName(configElement, WordTree.XML_ELEMENT_NAME);
				if (e != null) {
					configElement.replaceChild(wordTree.createXML(doc), e);
				} else {
					configElement.appendChild(wordTree.createXML(doc));
				}
			}

			DOMImplementationRegistry registry = DOMImplementationRegistry.newInstance();
	
			DOMImplementationLS impl = 
			    (DOMImplementationLS)registry.getDOMImplementation("LS");
			LSSerializer writer = impl.createLSSerializer();
			writer.getDomConfig().setParameter("format-pretty-print", Boolean.TRUE);
			LSOutput output = impl.createLSOutput();
			output.setEncoding("UTF-8");
			FileWriter fWriter = new FileWriter(configfile);
			output.setCharacterStream(fWriter);
			writer.write(doc.getDocumentElement(), output);
			fWriter.close();
		} catch(IllegalAccessException e) {
			e.printStackTrace();
		} catch(ClassNotFoundException e) {
			e.printStackTrace();
		} catch(InstantiationException e) {
			e.printStackTrace();
		}
	}
	
	public static void initialize(String configfile) {
		assert(instance == null);
		try {
			instance = new Experiment(configfile);
		} catch(IOException e) {
			e.printStackTrace();
		}
	}

	public static void initialize(InputStream configfile) {
		assert(instance == null);
		instance = new Experiment(configfile);
	}
	
	public static void initialize() {
		assert(instance == null);
		instance = new Experiment();
	}
	
	private Element getConfigElement() {
		Element rootElement = doc.getDocumentElement();
		if (rootElement == null) {
			rootElement = doc.createElement(XML_ROOT_ELEMENT_NAME);
			doc.appendChild(rootElement);
		}
		NodeList nodelist = rootElement.getElementsByTagName(XML_CONFIG_ELEMENT_NAME);
		Element configElement = null;
		if(nodelist == null || nodelist.getLength() != 1) {
			configElement = doc.createElement(XML_CONFIG_ELEMENT_NAME);
			rootElement.appendChild(configElement);
		} else {
			configElement = (Element) nodelist.item(0);	
		}
		return configElement;
	}
	
	private Element getConfigElement(String name) {
		Element configElement = getConfigElement();
		NodeList nodelist = configElement.getElementsByTagName(name);
		if (nodelist == null || nodelist.getLength() != 1) {
			Element elem = doc.createElement(name);
			configElement.appendChild(elem);
			return elem;
		}
		return (Element) nodelist.item(0);		
	}
	
	public Element getTrainingConfig() {
		return getConfigElement(XML_CONFIG_TRAINING_ELEMENT_NAME);
	}
	
	private Element getClassesConfig() {
		return getConfigElement(XML_CONFIG_CLASSES_ELEMENT_NAME);
	}
	
	public Element getTupleDescriptionConfig() {
		return getConfigElement(FactorTupleDescription.XML_ELEMENT_NAME);
	}
	
	@SuppressWarnings("unchecked")
	public Class<? extends AbstractTrainer> getTrainerClass() {
		Element element = getClassesConfig();
		try {
			Element classElement = XMLUtils.getFirstElementByTagName(element, XML_CONFIG_TRAINER_CLASS_ELEMENT_NAME);
			if (classElement == null) {
				return null;
			} 
			String classname = classElement.getTextContent();
			Class<? extends AbstractTrainer> cl = (Class<? extends AbstractTrainer>) Class.forName(classname);
			return cl.asSubclass(AbstractTrainer.class); 
		} catch(ClassNotFoundException e) {
			e.printStackTrace();
		} catch(Exception e) {
			e.printStackTrace();
		}
		System.exit(1);
		return null;
	}
	
	/**
	 * @return the tupleParser
	 */
	@SuppressWarnings("unchecked")
	public InputParser getTupleParser() {
		if (tupleParser == null) {
			Element element = getClassesConfig();
			try {
				String classname = element.getElementsByTagName(XML_CONFIG_PARSER_CLASS_ELEMENT_NAME).item(0).getTextContent();
				Class<? extends InputParser> cl = (Class<? extends InputParser>) Class.forName(classname);
				Constructor<? extends InputParser> con = cl.getConstructor(FactorTupleDescription.class);
				tupleParser = con.newInstance(getTupleDescription());
			} catch(NullPointerException e) {
				tupleParser = new FLMInputParser(getTupleDescription());
			} catch(ClassNotFoundException e) {
				e.printStackTrace();
				tupleParser = new FLMInputParser(getTupleDescription());
			} catch(Exception e) {
				e.printStackTrace();				
				tupleParser = new FLMInputParser(getTupleDescription());
			}			
		}
		return tupleParser;
	}

	/**
	 * @return the instance
	 */
	public static Experiment getInstance() {
		assert(instance != null);
		return instance;
	}

	private synchronized void loadForests() {
		loadLanguageModels();
		
		Element element = getConfigElement();
		NodeList nodes = XMLUtils.getChildrenElementsByTagName(element, ForestModel.XML_ELEMENT_NAME);
		for(int i=0; i<nodes.getLength(); ++i) {
			Element e = (Element) nodes.item(i);
			ForestModel forest = new ForestModel(e);
			forests.put(forest.getName(), forest);
		}
	}
	
	public ForestModel getForest(String name) {
		if (forests.isEmpty()) {
			loadForests();
		}
		return forests.get(name);
	}
	
	@SuppressWarnings("unchecked")
	private synchronized void loadLanguageModels() {
		if (LMs.size() > 0) return;
		
		String classname = XMLUtils.getFirstElementByTagName(getClassesConfig(), XML_CONFIG_LM_CLASS_ELEMENT_NAME).getTextContent();
		Constructor<LanguageModel> con = null;
		try {
			Class<LanguageModel> cl = (Class<LanguageModel>) Class.forName(classname);
			con = cl.getConstructor(Element.class);
		} catch (SecurityException e) {
			e.printStackTrace();
			return;
		} catch (ClassNotFoundException e) {
			e.printStackTrace();
			return;
		} catch (NoSuchMethodException e) {
			e.printStackTrace();
			return;
		}

		Element element = getConfigElement();
		NodeList nodes = XMLUtils.getChildrenElementsByTagName(element, LanguageModel.XML_ELEMENT_NAME);
		for(int i=0; i<nodes.getLength(); ++i) {
			Element lmElement = (Element)nodes.item(i);
			try {
				LanguageModel lm = con.newInstance(lmElement);
				lm.setIdNum(LMs.size());
				LMs.put(lm.getId(), lm);
				//System.err.printf("LM: %s, idnum=%d, backoff %s\n", forest.getId(), forest.getIdNum(), forest.getBackoffLM());
			} catch (IllegalArgumentException e) {
				e.printStackTrace();
			} catch (InstantiationException e) {
				e.printStackTrace();
			} catch (IllegalAccessException e) {
				e.printStackTrace();
			} catch (InvocationTargetException e) {
				e.printStackTrace();
			}
		}
		LMsById = new LanguageModel[LMs.size()];
		
		//lmIdSequence = new int[LMs.size()];
		//Arrays.fill(lmIdSequence, -1);
		
		for(LanguageModel lm : LMs.values()) {
			LMsById[lm.getIdNum()] = lm;
			/*
			boolean isPrimary = true;
			for(LanguageModel lm2 : LMs.values()) {
				if (forest.getId().equals(lm2.getBackoffLM())) {
					isPrimary = false;
					break;
				}
			}
			if (isPrimary) {
				// TODO: move it to a later stage where we know what LM is the first
				// in case there are multiple models that aren't backoff to anything...
				if (lmIdSequence[0] >= 0) {
					if (forest.getId().equals(LanguageModel.PRIMARY_LM_ID)) {
						lmIdSequence[0] = forest.getIdNum();
					} else if (LMsById[lmIdSequence[0]].getId().equals(LanguageModel.PRIMARY_LM_ID)) {
						// do nothing
					} else {
						System.err.println("unsure about the proper LM backoff sequence");
					}
				} else {
					lmIdSequence[0] = forest.getIdNum();
				}
			}
			*/
		}
		
		/*
		for(int i=0; i<LMs.size()-1; ++i) {
			String nextLm = LMsById[lmIdSequence[i]].getBackoffLM();
			if (nextLm == null || nextLm.isEmpty()) {
				if (i+1 < LMs.size()) {
					lmIdSequence = Arrays.copyOf(lmIdSequence, i+1);
				}
				break;
			}
			lmIdSequence[i+1] = LMs.get(nextLm).getIdNum();
		}
		*/
		/*
		System.err.print("LM id sequence:");
		for(int i=0;i<lmIdSequence.length; ++i) {
			System.err.printf(" %s(%d)", getLmByNumId(lmIdSequence[i]).getId(), lmIdSequence[i]);
		}
		System.err.println();
		*/
	}
	
	Element getLMConfig(String id) {
		Element configElement = getConfigElement();
		NodeList nodes = XMLUtils.getChildrenElementsByTagName(configElement, LanguageModel.XML_ELEMENT_NAME);
		for(int i=0; i<nodes.getLength(); ++i) {
			Element element = (Element) nodes.item(i);
			if (element.getAttribute(LanguageModel.XML_ATTR_ID_NAME).equals(id)) {
				return element;
			}
		}
		System.out.printf("getLMConfig(%s) failed\n", id);
		return null;
	}
	/**
	 * @return the lm
	 */
	public LanguageModel getLM(String id) {
		if (LMs.size() == 0) {
			loadLanguageModels();
		}
		return LMs.get(id);
	}

	public LanguageModel getLmByNumId(int numId) {
		return LMsById[numId];
	}
	
	public LanguageModel getLM() {
		return getLM(LanguageModel.PRIMARY_LM_ID);
	}
	
	public int getNumLMs() {
		return LMs.size();
	}
	
	public synchronized void addForest(ForestModel forest) {
		this.forests.put(forest.getName(), forest);
	}
	
	public synchronized void addLM(LanguageModel lm) {
		int id = LMsById == null ? 0 : LMsById.length;
		lm.setIdNum(id);
		if (LMs == null) {
			LMs = new HashMap<String, LanguageModel>();
		}
		LMs.put(lm.getId(), lm);
		if (LMsById == null) {
			LMsById = new LanguageModel[1];
		} else {
			LMsById = Arrays.copyOf(LMsById, LMsById.length+1);
		}
		LMsById[id] = lm;
	}
	/**
	 * @param forest the forest to set
	 */
	public void setLM(LanguageModel lm) {
		LMs.put(lm.getId(), lm);
	}
	
	
	/**
	 * @param tupleParser the tupleParser to set
	 */
	public void setTupleParser(InputParser tupleParser) {
		this.tupleParser = tupleParser;
	}

	/**
	 * @return the tupleDescription
	 */
	public FactorTupleDescription getTupleDescription() {
		if (tupleDescription == null) {
			Element descElem = getTupleDescriptionConfig();
			tupleDescription = new FactorTupleDescription(descElem);
			FactorTuple.setDescription(tupleDescription);
		}
		return tupleDescription;
	}

	/**
	 * @param tupleDescription the tupleDescription to set
	 */
	public void setTupleDescription(FactorTupleDescription tupleDescription) {
		this.tupleDescription = tupleDescription;
		FactorTuple.setDescription(tupleDescription);
	}
	
	private synchronized void loadHFT() {
		if (hft != null) return;
		
		Element configElement = getConfigElement();
		
		Element element = XMLUtils.getFirstElementByTagName(configElement, HFT.XML_ELEMENT_NAME);
		if (element != null) {
			hft = new HFT<HFTPayload>(element);
		}
	}
	
	public HFT<HFTPayload> getHFT() {
		if (hft == null) loadHFT();
		return hft;
	}

	public void setHFT(HFT<HFTPayload> hft) {
		this.hft = hft;
	}

	private synchronized void loadWordTree() {
		if (wordTree != null) return;
		Element configElement = getConfigElement();
		
		Element element = XMLUtils.getFirstElementByTagName(configElement, WordTree.XML_ELEMENT_NAME);
		if (element != null) {
			wordTree = new WordTree<WordTreePayload>(element);
		}
	}
	
	public WordTree<WordTreePayload> getWordTree() {
		if (wordTree == null) loadWordTree();
		return wordTree;
	}

	public void setWordTree(WordTree<WordTreePayload> wordTree) {
		this.wordTree = wordTree;
	}

	private static int compactFactors2Int(byte[] bytes) {
		int result = 0;
		for(int i=0; i<bytes.length; ++i) {
			// prevent sign expansion
			int b = 0xFF & bytes[i]; 
			result |= b << (i * 8); 
		}
		return result;
	}
	
	public void buildPrefixes() {
		if (hiddenPrefixes != null) return;
		getTupleDescription();
		
		int numPrefixes = 1 << tupleDescription.getCompactHiddenFactorsSize();
		hiddenPrefixes = new HashMap<FactorTuple, BinaryPrefix>(numPrefixes - 1);
		compactHiddenPrefixes = new BinaryPrefix[numPrefixes];
		prefix2CompactHiddenFactors = new HashMap<BinaryPrefix, byte[]>(numPrefixes - 1);
		final long hiddenMask = tupleDescription.getHiddenFactorsMask();
		
		BinaryTreeFinder<HFTPayload> finder = new BinaryTreeFinder<HFTPayload>() {
			public boolean apply(BinaryTree<HFTPayload> node) {
				HFTPayload payload = node.getPayload();
				if (payload.tuple != 0) {
					BinaryPrefix prefix = getCachedPrefix(payload.prefix);
					FactorTuple tuple = new FactorTuple(payload.tuple & hiddenMask);
					hiddenPrefixes.put(tuple, prefix);
					byte[] compact = tupleDescription.packHiddenFactors(tuple.getBits());
					prefix2CompactHiddenFactors.put(prefix, compact);
					compactHiddenPrefixes[compactFactors2Int(compact)] = prefix;
				}
				return false;
			}
		};
		getHFT().getTree().searchPostorder(finder);
	}
	
	public BinaryPrefix getHiddenPrefix(long hiddenFactors) {
		FactorTuple tuple = new FactorTuple(hiddenFactors & FactorTuple.getHiddenMask());
		BinaryPrefix p = hiddenPrefixes.get(tuple);
		if (p == null || p.getSize() == 0) {
			System.out.printf("NULL/Empty HFT prefix: %s\n", tuple.toStringNoNull());
		}
		return p;
	}
	
	public BinaryPrefix getHiddenPrefix(FactorTuple hiddenFactors) {
		return getHiddenPrefix(hiddenFactors.getBits());
	}
	
	public Map<FactorTuple, BinaryPrefix> getHiddenPrefixes() {
		return hiddenPrefixes;
	}
	
	public BinaryPrefix getPrefixByCompact(byte[] factors) {
		BinaryPrefix prefix = compactHiddenPrefixes[compactFactors2Int(factors)];
		assert(prefix != null);
		return prefix;
	}
	
	public byte[] getCompactFactors(BinaryPrefix prefix) {
		return prefix2CompactHiddenFactors.get(prefix);
	}
	
	public void buildWordPrefixes() {
		if (wordPrefixes != null) return;
		if (getWordTree() == null) return;
		FactorTupleDescription desc = Experiment.getInstance().getTupleDescription();
		byte idx = desc.getFactorIndex(getWordTree().getWordFactor());
		final edu.umd.clip.lm.factors.Dictionary dict = desc.getDictionary(idx);
		wordPrefixes = new BinaryPrefix[dict.size()];
		System.out.printf("num word prefixes: %d\n", dict.size());
		
		BinaryTreeFinder<WordTreePayload> finder = new BinaryTreeFinder<WordTreePayload>() {
			public boolean apply(BinaryTree<WordTreePayload> node) {
				WordTreePayload payload = node.getPayload();
				if (payload.word != null && !payload.word.equals("")) {
					//System.out.printf("in-tree wordPrefix[%s] = %s\n", payload.word, payload.prefix.toString());
					wordPrefixes[dict.getId(payload.word)] = getCachedPrefix(payload.prefix);
				}
				return false;
			}
		};
		getWordTree().getTree().searchPostorder(finder);
		/*
		for(int i=0; i<dict.size(); ++i) {
			if (wordPrefixes[i] == null) {
				System.out.printf("prefix[%s] = NULL\n", dict.getWord(i));
			} else {
				System.out.printf("prefix[%s] = %s\n", dict.getWord(i), wordPrefixes[i].toString());
			}
		}
		*/
	}
	
	public BinaryPrefix getWordPrefix(int value) {
		if (wordPrefixes == null) return null;
		if (wordPrefixes[value] == null) {
			FactorTupleDescription desc = Experiment.getInstance().getTupleDescription();
			byte idx = desc.getFactorIndex(wordTree.getWordFactor());
			System.out.printf("cannot find word prefix for '%s'\n", desc.getDescription(idx).getDictionary().getWord(value));
		}
		return wordPrefixes[value];
	}

	public synchronized BinaryPrefix getCachedPrefix(BinaryPrefix prefix) {
		BinaryPrefix p = prefixCache.get(prefix);
		if (p == null) {
			prefixCache.put(prefix, prefix);
			return prefix;
		}
		return p;
	}

	public BinaryPrefix[] getTags(byte tagFactor) {
		FactorDescription tagDesc = getTupleDescription().getDescription(tagFactor);
		BinaryPrefix tagPrefixes[] = new BinaryPrefix[tagDesc.getDictionary().size()];
		BinaryTree<HFTPayload> hft = getHFT().getTree();

		for(BinaryTreeIterator<HFTPayload> i = hft.getPreOrderIterator(); i.hasNext();) {
			BinaryTree<HFTPayload> node = i.nextNode();
			HFTPayload payload = node.getPayload();
			if (payload == null || payload.tuple == 0) continue;
			int val = FactorTuple.getValue(payload.tuple, tagFactor);
			if (val == Dictionary.getNull()) continue;
			if (tagPrefixes[val] != null) continue;
			
			long bits = payload.tuple & FactorTuple.getHiddenMask();

			//System.out.printf("bits: %s, prefix: %s\n", FactorTuple.toStringNoNull(bits), payload.prefix);
			
			// a work around: older HFTs seem to have S-<unk> for some reason
			for(byte idx : getTupleDescription().getHiddenFactors()) {
				if (idx != tagFactor) {
					bits = FactorTuple.setValue(bits, idx, Dictionary.getNull());
				}
			}
			if (FactorTuple.setValue(0, tagFactor, val) == bits) {
				// if it's the only non-null tag
				tagPrefixes[val] = payload.prefix;
				//System.out.printf("bits: %s, tag: %s, prefix: %s\n", FactorTuple.toStringNoNull(bits), 
				//		tagDesc.getDictionary().getWord(val), payload.prefix);
			}
		}
		return tagPrefixes;
	}
	
	public int getDebugDecoder() {
		return debugDecoder;
	}

	public void setDebugDecoder(int debugDecoder) {
		this.debugDecoder = debugDecoder;
	}

	public Map<String, ForestModel> getForests() {
		return forests;
	}
}
